package one.collectionAndMap;

import java.util.HashMap;
import java.util.Map;

/**
 两数之和
 时间复杂度：O(n）
 思路：哈希表解决
 枚举一个数x，找它前面有没有target-x。所以建立一个“数值到下标的Hashmap”就可以了。
 对于每个数x，先查询target-x，在插入x
 */
public class TwoSum {

    public int[] twoSum(int[] nums, int target) {

        Map<Integer, Integer> val_to_index = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(val_to_index.containsKey(target - nums[i])){ //本质上是在i之前查找，防止查找i本身
                return new int[]{i, val_to_index.get(target - nums[i])};
            }
            val_to_index.put(nums[i], i); //边循环i，边插入，维护的是对于nums[0, ..., n-1]的映射
        }
        return null;
    }
}
